package com.zy.algorithm.sort;

import java.util.Arrays;
import java.util.List;

/**
 * @author ZhaoYi
 * @date 2023/12/14 16:15
 * 插入排序（Insertion Sort）：
 * <p>
 * 思想：将未排序部分的元素一个个插入到已排序部分的正确位置上。
 * 特点：时间复杂度为O(n^2)，对于部分有序的数组效果较好。
 * <p>
 * 插入排序和选择排序是两种简单的排序算法
 * 思想：
 * 插入排序：从未排序部分依次取出一个元素，插入到已排序部分的正确位置上，最终完成整个序列的排序。
 * 选择排序：每次从未排序部分中选择最小的（或最大的）元素，与未排序部分的第一个元素交换位置，从而逐步形成已排序部分。
 * <p>
 * <p>
 * 操作次数：
 * 插入排序：对于部分有序的数组，插入排序的操作次数相对较少。
 * 选择排序：不论数组是有序还是无序，选择排序的操作次数都是相同的。
 * <p>
 * <p>
 * 适用情况：
 * 插入排序：适合对部分有序的数组进行排序，或者需要动态添加新元素时维持有序性的场景。
 * 选择排序：适合对小型数据集进行排序，或者对稳定性不做要求的场景。
 * <p>
 * <p>
 * 稳定性：
 * 插入排序：稳定，相同元素的顺序在排序后不会改变。
 * 选择排序：不稳定，相同元素的顺序可能会改变。
 * <p>
 * <p>
 * 时间复杂度：
 * 插入排序：平均时间复杂度为O(n^2)。
 * 选择排序：平均时间复杂度也为O(n^2)。
 * 但在不同的情况下具有不同的优势。
 * 插入排序对部分有序的数组效果好，适合对动态数据进行排序；
 * 而选择排序在排序规模较小或者对稳定性要求不高的情况下比较合适。
 */
public class InsertionSort<T extends Comparable<? super T>> implements ISort<T> {
    @Override
    public List<T> sort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return list;
        }

        //已经有序的部分下标
        int finish = 0;
        for (int i = finish + 1; i < list.size(); i++) {
            T t = list.get(i);

            //在有序集合中放入正确的位置
            for (int j = 0; j <= finish; j++) {
                T tt = list.get(j);
                if (t.compareTo(tt) < 0) {
                    //平移插入
                    inserts(list, j, i);
                    break;
                }
            }

            //都比t小 不用管相当于 放最后  [428, 29, 378, 143, 711, 912, 625, 520, 144, 676, 901, 336, 74, 342, 683, 669, 866, 195, 257, 517, 687, 367, 214, 490, 998, 990, 41, 134]
            finish++;

        }

        return list;
    }

    private void inserts(List<T> list, int j, int i) {
        T tmp = list.get(i);
        //倒着移动才对
        for (int k = i; k > j; k--) {
            list.set(k, list.get(k-1));
        }
        list.set(j, tmp);
        System.out.println("平移完有序部分: " + Arrays.toString(list.subList(0, i).toArray()));
    }
}
